Bus arbitration means a systematic way of deciding, which of a number of contending nodes is allowed to transmit on a bus, and making the contending nodes act in accordance with the decision. There are two basic approaches to bus arbitration. Centralized arbitration involves a centralized decision-making entity, which grants the nodes turns for accessing the bus according to need. Distributed arbitration relies on the nodes' own ability to detect contention situations and to react accordingly. Examples of centralized arbitration are known from the standardized PCI (Peripheral Component Interconnect) and VMEbus (Versa Module Eurocard bus) solutions. Known parallel bus standards with distributed arbitration include NuBus and MultiBus II, and known serial bus standards with distributed arbitration include the i2c (or IIC; Inter-Integrated Circuit), CAN (Controller Area Network), and LIN (Local Interconnect Network).
FIG. 1 illustrates an exemplary environment where bus arbitration will be needed. This example is known from publication T. Vallius and J. Roning: “ATOMI II—Framework for easy building of object oriented embedded systems”, proceedings of 9th Euromicro Conference on Digital System Design, Architectures, Methods and Tools, Cavtat, Croatia, Aug. 30-Sep. 1, 2006 as the EOC (Embedded Object Concept) and it is particularly suitable for building embedded systems in a modular and object-oriented manner from blocks. A class object, like those illustrated with reference designators 101 and 141, represents on a logical level a whole class of objects. In the first object class there are the class object 101 and the objects illustrated with reference designators 111, 121, and 131. In the second object class there are the class object 141 and the objects illustrated with reference designators 151 and 161. Each class object and object is assumed to contain some functional parts 102, 112, 122, 132, 142, 152, and 162 respectively. A first bus 171 links the class objects to each other. For this purpose each class object 101 and 141 has a first bus interface 103 and 143 respectively. Within each class there is a class-specific bus, of which buses 181 and 191 are shown. The class object and the objects of the class all contain a bus interface for connecting them to the appropriate bus; see bus interfaces 104, 113, 123, 133, 144, 153, and 163 respectively. Bus-specific arbitration is needed separately on each of the buses 171, 181, and 191.
An essential feature of centralized arbitration is the fact that it is not scalable to a higher number of nodes than a certain relatively low limit, because it requires an individual arbitration connection from each node to the decision-making device. The modular, object-oriented architecture of FIG. 1 is freely scalable in respect of both the number of object classes and the number of objects in a class, which makes distributed arbitration the only plausible alternative.
Several basic approaches are known for distributed arbitration. The designation “open-collector gates” refers to a system in which one of the digital states of a bus line is the so-called weak state, while the other is the forced state. Typically a high voltage state is weak and the low voltage state is forced. Two simultaneous settings on such a bus line will always result in the bus line assuming the forced state. Each transmitting node monitors the results of the transmissions on the bus line. If a transmitting node attempted to set the bus line to the weak state but finds the bus line in the forced state instead, it knows that another node is also transmitting and reacts by ceding the bus and trying again later. The drawback of open-collector gates is the increasing energy consumption as a function of the number of nodes. The more nodes there are, the more power is needed to pull the voltage on the bus line to the forced state against the inverse effect of the pull-up resistors in the other nodes.
Daisy chaining refers to drawing a common arbitration line through all possible masters of the bus. An access request goes through every master, which can forward or stop it. As a drawback, many daisy chain solutions require relatively complicated arbitration logic in each node. A token ring approach is conceptually somewhat related to daisy chaining and involves circulating a transmission-authorising token among the nodes.
In carrier sense multi-access/collision detection (CSMA/CD) the nodes listen to the bus and only begin transmitting if the bus appears to be free. Every now and then two or more nodes begin their transmissions simultaneously, which results in a collision. Each node waits a random time after a collision before trying again. A lot of bus capacity is easily lost especially if there continuously many masters competing for the bus. Time sliced arbitration or time division arbitration means making predetermined allocations about transmission turns. It requires the nodes to have access to a common clock, and wastes capacity in those cases where the actual transmission activity is not evenly distributed among nodes.